package gold.utils;

public class Trie {

    public class Node {
        boolean isWord;
        Node[] children;

        public Node(boolean isWord) {
            this.isWord = isWord;
            children = new Node[26];
        }
    }

    private Node root;

    public Trie() {
        this.root = new Node(false);
    }

    public void insert(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Node(false);
            }
            node = node.children[idx];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        return search(word, 0, 0, root);
    }

    private boolean search(String word, int i, int misMatchCount, Node root) {
        if (misMatchCount > 1) {
            return false;// mismatch too much.
        }

        if (i == word.length()) {
            return misMatchCount == 1 && root.isWord;//mismatch just once and is final.
        }

        char c = word.charAt(i);
        int idx = c - 'a';
        for (int j = 0; j < 26; j++) {
            if (root.children[j] == null) {
                continue;
            }
            if (idx == j) {
                if (search(word, i + 1, misMatchCount, root.children[j])) {
                    return true;
                }
            } else if (search(word, i + 1, misMatchCount + 1, root.children[j])) {
                return true;
            }
        }

        //如果当前字符没有后继者，并且word还没遍历完，则意味着不可能完成匹配
        return false;
    }
}
